perm filename OCCULT[0,BGB]6 blob
sn#116833 filedate 1974-08-29 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00016 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00003 00002 {F8⊂C<N αOCCULT λ30 P46 I425,0 JC FA} SECTION 4.
C00009 00003
C00012 00004 ⊂4.1 Initialization and Culling.⊃
C00014 00005
C00017 00006
C00019 00007
C00022 00008
C00026 00009 ⊂4.2 Hide Marking a Coherent Object.⊃
C00031 00010 ⊂4.3 Edge-Edge and Face-Vertex Comparing.⊃
C00034 00011 An alternate edge-edge compare method would be to solve the
C00040 00012
C00041 00013 ⊂4.4 Recursive Windowing.⊃
C00049 00014
C00053 00015 {I135,0JC} FIGURE 4.6 - EXAMPLE OF VIDEO SYNTHESIS.
C00056 00016 ⊂4.6 Performance of OCCULT and Related Work.⊃
C00059 ENDMK
C⊗;
{F8;⊂C;<N; αOCCULT; λ30; P46; I425,0; JC; FA} SECTION 4.
{JC; FD} HIDDEN LINE ELIMINATION FOR COMPUTER VISION.
{λ7; W250; JA; FA}
4.0 Introduction to Hidden Line Elimination.
4.1 Initialization and Culling.
4.2 Hide Marking a Coherent Object.
4.3 Edge-Edge and Face-Vertex Comparing.
4.4 Recursive Windowing.
4.5 Photometric Modeling and Video Generation.
4.6 Performance of OCCULT and Related Work.
{λ30;W0;I950,0;JUFA}
⊂4.0 Introduction to Hidden Line Elimination.⊃
Hidden line elimination refers to the process of simulating
the appearance of opaque three dimensional objects. The phrase
<hidden line elimination> dates from when the problem only involved
deleting the undesired, that is the <hidden> lines, from a line
drawing (Figure 4.1); today the phrase persists but connotes the
wider problem of synthesizing realistic images using a computer. The
present discussion is about techniques which have been implemented in
a particular hidden line eliminator named OCCULT, from the Latin word
<occultare> meaning <to hide>. OCCULT illustrates novel solutions to
the graphics problems of exploiting object coherence and image
coherence, of combining image space with model space techniques,
and of sorting faces, edges and vertices in two dimensions.
OCCULT is further characterized by its intended application
to computer vision and robotics. The distinguishing design
requirement of a hidden line eliminator intended for vision is that
it must maintain back pointers from the final 2-D images to the
initial 3-D models so that the identity of features can be recovered.
In computer graphics, the results of hidden line elimination are
intended for human viewing so the correspondence between the image
and the model is not usually retained (unless image based model
editing is being attempted). Another design goal for OCCULT was to
output a connected graph of regions, edges and vertices that covers
the image with no holes missing, no regions overlapping and no
dangling edges. It was naively assumed that such a highly structured
image representation, called a <mosaic image>, would provide a
suitable basis for deriving features such as the location and orientation
of high contrast edges without having to generate video images.
{I∂30,0;FCJC} FIGURE 4.1 - EXAMPLE OF HIDDEN LINE ELIMINATION.
{I∂375,630;H2;X1.2;*41.1;*41.2;
I∂80,0;W0,630;JCFA} BEFORE {I∂0,631;W630,1260;JC} AFTER {W0,1260;I∂30,0;JUFA}
Hidden line eliminators appear in two previous vision
systems: one by Roberts (63) and the other by Falk (70); the present
system is a direct heir of the work of Falk in that the last version
of the Falk system contained one of the first versions of OCCULT
(installed by Richard Orban). As with image analysis, image synthesis
(i.e. hidden line elimination), is a perennial research problem
because it cannot be fully isolated from physical modeling.
Metaphorically, hidden line elimination is the visible tip of the
iceberg of physical simulation. The weaknesses of the underlying
model literally show up in passing through the process of image
synthesis. The present day collection of techniques is still quite
lacking in realism, economy, flexibility and even reliability.
OCCULT is not a simple hidden line eliminator. In overall
structure it is a combination of five techniques, Box 4.1. The first
method, called <culling>, eliminates portions of the model which are
hidden because of some easy to compute heuristic reason. The cull
heuristics (detailed in Section 4.1) include: elimination by clipping
planes, elimination by face vectors, elimination by inspection of
concave corners, and elimination by previous occultation. After the
culls have been applied, the next three techniques are arranged in a
three level heirarchy which comprises the main part of OCCULT. At
the outermost level there is a Warnock (68) like recursive windowing
method, which calls an edge-edge comparing method on small enough
windows, which in turn calls a coherent object tracing method to
split off and mark the portions of an object that are hidden. The
methods are explained in bottom-up order: hide tracing in Section
4.2, edge-edge comparing in Section 4.3 and recursive windowing in
Section 4.4. The fifth technique is a face-vertex compare method
that is occasionally required to solve a particular class of cases
that are missed by the edge-edge compare. The difficult part in
building an OCCULT like hidden line eliminator lies in getting all
the unruly beasts in harness together; the mystery being that no one
beast is sufficiently strong to carry the whole burden by itself.
{|λ10;JAT400;}
BOX 4.1{JC} THE FIVE HIDDEN LINE ELIMINATION TECHNIQUES OF OCCULT.
1. Initialization Hide Culling.
2. Recursive Windowing.
3. Coherent Object Hide Tracing.
4. Edge-Edge Comparing.
5. Face-Vertex Comparing.
{|λ30;T-1;JUFA}
⊂4.1 Initialization and Culling.⊃
A substantial part of sophisticated hidden line elimination
lies in careful attention to initial preparations. As it has now
stood for the past two years, OCCULT has two input restrictions
imposed for the sake of execution speed: no conflicting bodies are
allowed and no concave faces are allowed. Conflicting bodies are
those that occupy the same space at the same time; concave faces are
faces with interiors containing a pair of points such that the line
segment between the points is not contained in the face. The
rational for both these restrictions is based on the optimization
technique of getting computations out of inner loops; conflicting
bodies and concave faces can be eliminated by employing certain
polyhedral construction primitives prior to hidden line elimination.
The restrictions are not inherent limitations of any of the
techniques in OCCULT, so that a less restricted but slower
implementation is feasible.
OCCULT is a marking algorithm, the temporary marking bits are
listed in Box 4.2. The combination (POTENT and ¬VISIBLE) means
potentially visible; (¬POTENT and VISIBLE) means actually visible;
(¬POTENT and ¬VISIBLE) means hidden; and the combination (POTENT and
VISIBLE) is an unused state that happens to be interpreted as
VISIBLE.
{|λ10;JAT200,500;}
BOX 4.2{JCFA} STATUS BITS FOR OCCULT MARKINGS.
POTENT∞.Potentially Visible Entity.
VISIBLE∞.Actually Visible Entity.
PZZ∞.Behind the camera image plane, Positive Zcc.
NZZ∞.Before the camera image plane, Negative Zcc.
TMPBIT∞.Temporary Split edge of vertex.
FOLDED∞.Edge with only one POTENT face.
JOTBIT∞.Joint over T vertex.
JUTBIT∞.Joint under T vertex.
{|λ30;T-1;JUFA}
The initialization is performed in three steps: (1).
vertex marking and vertex perspective projection; (2). face marking,
face Z-clipping, and computation of face coefficients; and (3).
edge marking and computation of edge coefficients. Two cull
heuristics are done during the initialization: clipping and backside
face elimination; and the other two culls are done immediately
afterwards: concave corners check and the hide last hidden check.
Vertex initialization includes the prespective projection of
every vertex in the model and the marking of every vertex that is in
front of the camera as POTENT (potentially visible) if its
perspective projected Z coordinate, ZPP(V), is greater than the
simulated image plane distance, FOCAL. Two further status bits,
named PZZ and NZZ, indicate positive ZCC (camera coordinates) or
negative ZCC are inclusive ORed into all the faces and edges of each
vertex for the sake of the Z-clipper.
Face initialization consists of Z-clipping: if a face has
only its NZZ bit turned on, then it is completely behind the camera
and is immediately dropped from all futher condsideration (i.e.
culled out); if the face has both its PZZ and its NZZ turn on then it
is Z-clipped by using the camera's image plane as a cutting plane.
Next for faces in view of the camera, the 3-D perspective projected
face coefficients are computed (equations given below) and the faces
with their backsides towards the camera are culled out (Figure 4.2);
faces surviving to this point are marked as POTENT and are placed
into a list of faces of the first window of the recursive window
sort.
Edge initialization consists of computing the normalized 2-D
edge coefficients (equation given below) and of marking the edge as
FOLDED or ¬FOLDED depending on whether it has one face POTENT or two
faces POTENT, respectively. FOLDED edges are then inverted if
necessary so that the POTENT face is the PFACE. Folded edges are
illustrated in the rightmost panel of Figure 4.2. The <folded edges>
are called <contour edges> by Appel(71) and Sutherland(73). The
folded bit is passed along to (inclusive ORed into) the vertices of
folded edges.
{|λ10;JA}
BOX 4.3{FAJC} Normalized 3-D Face Coefficients:{λ10;JAF3}
E ← PED(F);V1 ← VCW(E,F);V2 ← VCCW(E,F); E ← ECCW(E,F);V3 ← VCCW(E,F);
KK(F) ← XPP(V1)*(ZPP(V2)*YPP(V3)-YPP(V2)*ZPP(V3))
+ YPP(V1)*(XPP(V2)*ZPP(V3)-ZPP(V2)*XPP(V3))
+ ZPP(V1)*(YPP(V2)*XPP(V3)-XPP(V2)*YPP(V3));
AA(F) ← (ZPP(V1)*(YPP(V2)-YPP(V3)) + ZPP(V2)*(YPP(V3)-YPP(V1)) + ZPP(V3)*(YPP(V1)-YPP(V2)));
BB(F) ← (XPP(V1)*(ZPP(V2)-ZPP(V3)) + XPP(V2)*(ZPP(V3)-ZPP(V1)) + XPP(V3)*(ZPP(V1)-ZPP(V2)));
CC(F) ← (XPP(V1)*(YPP(V3)-YPP(V2)) + XPP(V2)*(YPP(V1)-YPP(V3)) + XPP(V3)*(YPP(V2)-YPP(V1)));
TMP ← 1/SQRT(AA(E)↑2 + BB(F)↑2 + CC(F)↑2);
AA(F) ← TMP*AA(F);BB(F) ← TMP*BB(F);CC(F) ← TMP*CC(F);
{FAJC} Normalized 2-D Edge Coefficients:{λ10;JAF3}
AA(E) ← YPP(PVT(E)) - YPP(NVT(E));
BB(E) ← XPP(NVT(E)) - XPP(PVT(E));
CC(E) ← XPP(PVT(E))*YPP(NVT(E)) - XPP(NVT(E))*YPP(PVT(E));
TMP ← SQRT(AA(E)↑2 + BB(E)↑2);
AA(E) ← AA(E)/TMP; BB(E) ← BB(E)/TMP; CC(E) ← CC(E)/TMP;
{|λ30;JUFA}
{I∂20,0;FCJC} FIGURE 4.2 - FRONT FACES AND FOLDED EDGES.{
X0.41;H2;I∂-10,0;⊗42.1;I∂0,420;⊗42.2;I∂0,840;⊗42.3;I∂350,0;JUFA}
After face, edge and vertex initialization two culls are
applicable. The concave corner cull checks folded vertices of valence
four or more for edges of the vertex that are hidden by a face of the
same vertex; the corner marked by a heavy dot in Figure 4.3 is a
concave corner with two folded edges that are easily discovered to be
hidden (i.e the end of the edge that is connected to the corner is
hidden by a face of that corner). The second cull is applicable when
hidden line elimination is being done on a sequence of images which
are not changing very much from one picture to the next. By saving a
pointer to the <overface> that covered each hidden vertex in the
immediately preceding hidden line elimination, the previous overface
can be quickly checked to see if it still covers the vertex. In the
case of arm animation (example #2, Section 3.0) this form of
exploiting <frame-coherence> realized a twenty-five percent savings
in computation time (under timesharing, but with no other user
programs).
{I∂-30,0;FCJC} FIGURE 4.3 - FRONT FACES AND FOLDS OF A CONCAVE CORNER.{
X0.307617;H2;I∂-10,0;⊗43.1;I∂0,∂315;⊗43.2;I∂0,∂315;⊗43.3;i∂0,∂315;⊗43.4;
H3;I∂141,172;C5;I∂0,∂315;C5;I∂0,∂315;C5;I∂0,∂315;C5;I∂140,0;JUFA}
Inspite of the complexity explained so far, still further
measures could be taken to make the hidden line eliminator even
faster, For example more 3-D clipping or spatial recusive cell
sorting would allow the earlier elimination of objects that are
out of sight.
⊂4.2 Hide Marking a Coherent Object.⊃
OCCULT marks the faces, edges and vertices of a polyhedral
scene as being either visible or hidden with respect to a simulated
camera. Edges that were at first partially visible are split into
pieces so that each piece is either fully visible or fully hidden.
All splits are undone and all OCCULT bits are cleared by a fixup
routine named UNCULT. In a modeling environment that provides
coherent polyhedra that can be easily traveled and modified, the
simple technique of hide marking the neighbors of entities already
hidden can be used to do almost all of the actual hiding, once a
starting place has been found.
In OCCULT, the two innermost routines, EHIDE and VHIDE,
perform this kind of marking and splitting.
The routine VHIDE takes two arguments:
the vertex, V, which is to be marked as hidden and the face, F, that
is known to hide V; the routine then simply calls EHIDE for each
potentially visible edge of V's perimeter. EHIDE in turn takes three
arguments: an overface, F, an edge, E, and one vertex, V, of that
edge which is known to be hidden by F. EHIDE then checks to see
whether or not E leaves its overface, F, there are three basic cases:
(i) E does not leave F, so it is marked as hidden and VHIDE is
applied to the vertex OTHER(E,V); (ii) E does leave overface F by
crossing under a ¬FOLDED edge which provides a new overface for EHIDE
to check; or (iii) E leaves F by crossing under a folded edge, so
EHIDE splits the original edge, E, and the folded edge to form a
T-joint (explained below) marking the hidden portion of E
as hidden and leaving the remaining portion of E potentially visible.
A T-joint occurs in the image, when a folded edge hides a
second edge that is further away from the camera. When OCCULT
discovers a T-joint, both edges are ESPLIT and two new vertices are
created the further one is called the JUT, Joint-Under-T, vertex the
nearer one is called the JOT, Joint-Over-T, vertex. Juts and Jots point
at each other using a temporary link field named TJOINT.
{FCJC} FIGURE 4.4 - T-JOINT DIAGRAM.{JUF8}
{JC} (The diagram is a view from slightly to the left and below the camera from which JOT and JUT appear coincident.)
{JUFA;I∂-20,0;↓FA;H4;
I∂175,∂350;C7;↓I∂-5,∂10;}EDGE{↑V∂0,∂240;C7;↓I∂35,∂-60;}JUT{↑
V∂0,∂40;H1;V∂0,∂250;
H4;C7;↑↓;I∂10,∂630;↓I∂35,∂5;}FOLD{↑
V∂1,∂0;C7;V∂130,∂0;C7;↓I∂0,∂20;}JOT{↑V∂170,∂0;C7;↑;I∂300,0;}
There are several techniques for finding hidden starting
places, the major techniques involve doing an edge-edge or a
face-vertex compare using all the potentially visible faces, edges
and vertices; the minor techniques include the concave corner cull
and the hidden on last hide cull.
⊂4.3 Edge-Edge and Face-Vertex Comparing.⊃
In OCCULT, two particular compares stand out as most basic,
the edge-edge compare and the face-vertex compare which are
implemented in procedures named COMPEE and COMPFV, respectively. The
edge-edge compare routine, COMPEE, determines whether or not two
edges intersect in the 2-D image coordinates, XPP and YPP. The
basic edge-edge intersection test requires passing two opposition
conditions: the ends of one edge must be in the opposite halfplane
with respect to the line containing the other edge and vice versa.
Halfplane opposition is checked by two evaluating the normal equation
of the line using the edge coefficients AA, BB, CC and the vertex
coordinates XPP and YPP. Consequently, it can be assumed that the
two edges cross if the following expressions both return negative
values:
{λ7;JAF3
} FLAG1 ← (AA(E1)*XPP(PVT(E2)) + BB(E1)*YPP(PVT(E2)) + CC(E1))
XOR (AA(E1)*XPP(NVT(E2)) + BB(E1)*YPP(NVT(E2)) + CC(E1));
FLAG2 ← (AA(E2)*XPP(PVT(E1)) + BB(E2)*YPP(PVT(E1)) + CC(E2))
XOR (AA(E2)*XPP(NVT(E1)) + BB(E2)*YPP(NVT(E1)) + CC(E2));{λ30;JUFA}
\The infix operator XOR (exclusive OR) is for toggling the sign bits
in the same fashion as a multiplication would in more conventional
ALGOL. When the crossing condition is true, the locus of intersection
can be computed by solving two equations in two unknowns:
{λ7;JAF3
} TMP ← (AA(E1)*BB(E2) - AA(E2)*BB(E1));
XPP(V) ← (CC(E1)*BB(E2) - CC(E2)*BB(E1))/TMP;
YPP(V) ← (AA(E1)*CC(E2) - AA(E2)*CC(E1))/TMP;{λ30;JUFA}
An alternate edge-edge compare method would be to solve the
two equations in two unknowns first and then to see whether the
intersection locus is interior to the line segments of both edges.
Since, disjoint pairs of edges occur much more frequently than
intersecting edges, the alternate method requires more floating
arithmetic on the average than the first method which can
discover about half of the disjoint cases by computing FLAG1.
Furthermore the alternate method does not lend itself to
distinguishing the almost touching cases which must be nudged to be disjoint.
The OCCULT design depends on coercing edges to intersect at one unique point
or not at all, the steps listed in Box 4.4 handle the special cases
requiste to such a crossing discipline. The nudge is done to the image
coordinates so that the accuracy of the world coordinates is uneffect.
{|;λ10;JAFA}
BOX 4.4 {JC} Edge-Edge Compare Steps.
i. Test for Identity: same edge twice.
ii. Test for Topological connection: Edges with vertex or T-joint in common.
iii. Test for span Overlap in XPP and YPP: To prevent nasty collinear cases.
iv. Compare for crossing: Opposition Tests and Crossing Solver.
v. Nudge (Move off line, towards right and down).
{|;λ30;JUFAQ}
The face-vertex compare routine, COMPFV has two parts:
<Z-depth compare> for vertex under the plane of the face, and <2-D
within compare> for vertex enclosure by the face perimeter. The first
compare is done by evaluating the Z-depth of the vertex with respect
to the plane of the face. The second compare tests whether the vertex
falls outside of the face with respect to any of the edges of the
face perimeter, since faces are convex and since polyhedra are
oriented the properly directed edges coefficient are available. The
Z-depth test is performed first because it is quicker.
Two very simple but important kinds of hidden line
eliminators (that almost work) are based on combining edge-edge
comparing or face-vertex comparing with coherent object hiding. In
the edge-edge compare method all the edges (or even merely all the
folded edges) of the image are compared with each other, N*(N-1)/2
compares, for crossings; when a crossing is found a T-joint is made
and the hidden portion of the under edge is given to an EHIDE
routine. In the face-vertex compare method all the vertices are
compared with all the faces, (face count)*(vertex count) compares,
for enclosure and covering; when a vertex is found hidden under and
within a face it is given to a VHIDE routine. Together the EE-compare
method and the FV-compare method form one slow but sure hidden line
elimination algorithm; alone the EE-method fails to detect hidden
objects with edges that don't intersect any edges of the occluding
object as in the left panel of Figure 4.5 which shows two bricks of
the same size but one behind the other. Likewise the FV-method fails
to detect hidden objects in scenes where no vertex of the object is
surround or covered by a face, right panel of Figure 4.5.
In OCCULT, the edge-edge compare is done after recursive
windowing has isolated a reasonably small number of edges (twelve). A
face-vertex compare is done only if any potentially visible vertices
remain after all the other techniques have finished; in particular
face-vertex comparing is only done when the case illustrated in the
left panel of Figure 4.5 actually occurs and the set of faces that
are used are only the faces that intersect the recursive window that
contains the vertex.
{Q;I135,0;FCJC} FIGURE 4.5 - EE AND FV UNDETECTED HIDDEN OBJECT CASES.
{I∂-100,0;H2;X0.61523;⊗45.1;I∂0;∂630;⊗45.2;
I∂580,0;W0,630;JCFA} EDGE-EDGE FAILURE CASE.{
I∂0,631;W630,1260;JC} FACE-VERTEX FAILURE CASE. {W0,1260;I∂30,0;JUFA}
⊂4.4 Recursive Windowing.⊃
Recursive Windowing is a two dimensional spatial sorting
technique for partitioning the faces, edges and vertices associated
with a rectangular region called a window into two subwindows. The
technique is applied recursively until a desired condition is
achieved. The usual termination condition is that the population of
entites in the window becomes sufficiently low or that the window
becomes extremely small. The idea is implement in a routine called
ESORT which resembles the hidden line eliminators of (Warnock 68) and
(Sutherland 69). However ESORT is unique in that it maintains a data
structure which allows edges to be split during the sort. The
potentially nasty fixups are accomplished using a data structure that
maintains a coherent image of both windows and edges. Metaphorically,
the data structure is a cloth with a warp of windows and a woof of
edges, where each warp thread is bound to a woof fiber by a bead.
<Window Structure>. The sort window itself is a twelve word
node which contains data fields named XLO, XHI, YLO and YHI which
specify the boundary of the window and data fields named PENCNT,
SURCNT, EDGCNT and VCNT which specify the number of faces that
penetrate the window, the number of faces that surround the window,
the number of edges that pass through the window and the number of
vertices that fall within the window, respectively. The window
contains link fields to hold pointers to the head of the
pen-face list (penetrating faces), the sur-face list (surrounding
faces), the vertex list, the head and tail the edge list and a
pointer to its antecedent window.
<Bead Structure>. A bead is a two word node that contains
four pointers and which represents one instance of an edge passing
through a window. Each edge has a list of beads representing an
ordered list of the windows through which it passes; and
each window has a list of beads representing a list of the edges it
contains. The link fields named WND and EDG of a bead, point to the
particular window and the particular edge to which the bead belongs.
The link fields named WNBL and EDBL of a bead contain the necessary
links for the window's bead list and for the edge's bead list.
{|;λ10;JAFA}
BOX 4.5 {JC} RECURSIVE WINDOWING ROUTINES.
1. MKSWN Make Sort Window.
2. PSHSWN Push Sort Window.
3. PENSUR Update penetrator and surrounder lists.
4. POPSWN Pop Sort Window.
5. BLED Bead List Edit.
{|;λ30;JUFA}
The actual sort is composed of five routines (Box 4.5) which
perform all the necessary creations and alterations to the
window/edge/bead data structure. Initialization is done by the make
sort window routine, MKSWN, which places all the potentially visible
faces, edges and vertices into the first sort window along with the
population counts and the extreme location of vertices in the
positive and negative, XPP and YPP directions.
If the population counts of the window are too large, the
pushdown sort windowing routine, PSHSWN, creates a new window node,
places the node into the sort-window pushdown list, halves the original
window's rectangle (spliting the longer sides) leaving the left (or
upper) half of the rectangle in the old window node and allocating
the right (or lower) half to the new window node. Next the vertex
list is partitioned, each vertex falls into only one or the other
window. Next the original window's bead list of penetrating edge is scanned,
each edge must fall into one or the other or both windows. If an edge
falls into both windows then a new bead is made and is placed in order
into the bead list of the edge so that the beads of every edge
indicate window penetrations in order from upper-left-most to
lower-right-most. Finally PSHSWN applies PENSUR to each of the two
windows. The penetrator and surrounder face routine, PENSUR, scans
the new bead lists of penetrating edges of the two subwindows and
marks the faces of those edges as penetrators and places them
on the pen-list of the new window; next the routine scans the old
penetrator list of the parent window and tests (and clears) the
markings. Unmarked faces must be either surrounders or outsiders; the
surrounders are placed in the sur-list of the new window.
If the populations of the window are sufficiently low the
hidden line eliminator (or the body intersector, Chapter 5) processes
the window (does the edge-edge compares) and calls the pop sort
window routine, POPSWN. POPSWN zeroes the window field, WND, of beads
of the window as an indication that the window is dead and so are its
beads; dead beads are returned to free storage by the BLED routine
explained below. Next the POPSWN scans the vertices or the window and
places the pen-list and sur-list pointers of the window into
temporary fields of each vertex; this trick preserves the results of
the recursive window sort for the sake of possible face-vertex
comparing. Finally the window node is popped off the pushdown window
list and returned to free storage.
During both hidden line elimination and body intersection,
edges are split in order to isolate the portion that is hidden or in
order to create face piercing points. When an edge is split its bead
list of windows is also split by means of the bead list edit routine,
BLED. Since beads of an edge are ordered upper-left to lower-right;
the BLED routine scans the beads for the window into which the newly
created split vertex falls within; the vertex is then placed on that
window's vertex list and a new bead is created (since both the old
and the new edges must have beads in the window that contains the
split) and the old bead list is split. Dead beads that are found
while scanning the bead list are returned to free storage.
Although the link manipulations are complicated to recite,
the essential point is that both windows and edges can be split
without losing their topological connectedness, which gives one a
tool for reducing an N-squared spatial computation into an N-log-N
computation. The present implementation is coded in PDP-10 machine
code, an ALGOL publication version will appear in a forthcoming
technical report which is beyond the scope of this paper.{Q}
{I135,0;JC} FIGURE 4.6 - EXAMPLE OF VIDEO SYNTHESIS.
{I560,630;*DEMO53;I∂240,0;JAFA}
⊂4.5 Photometric Modeling and Video Generation.⊃
The light scattering properties of ordinary surfaces can be modeled by
thinking of the surface as composed of many little mirrors. The orientation of
{JUFA}\each mirror is described by two angles, its tilt from the
normal vector of the surface and its pan about the normal vector with
respect to a specified reference vector in the tangent plane of the
surface. For a perfect reflecting surface all the differential
mirrors have a zero pan and tilt; for isotropic conventional surfaces
the statistical distribution of pan orientations is flat and the
distribution of tilt orientations is a blip function; and for a
perfect isotropic Lambert surfaces both the pan and tilt
distributions are flat.
After the visible faces have been assigned intensity values,
a conversion from an OCCULT mosaic image to a raster image is done by
an auxiliary program called MKVID, make video. MKVID resembles a
Gouraud (71) and Watkins(70) hidden line eliminator in that it fills
scan line by linear interpolation of segments between edges of the
mosaic which are in their turn linear interpolations between
vertices.
{Q}
⊂4.6 Performance of OCCULT and Related Work.⊃
Ten hidden line elimination techniques were recently surveyed
in (Sutherland, Sproull and Schumacker 1973), which after emphasing
that hidden line elimination can be viewed as a sorting problem
concluded with the remark that future implementations should be based
on exploiting frame coherence, object coherence and combinations of
the existing techniques. However the survey paper might be inadquate
for a would-be implementer who should consult the textbook by
(Sproull and Newman 73) for detailed explainations of the Warnock
method and the Watkins method. Original research reports on hidden
line elimators include: (Roberts 63), (Appel 67), (Warnock 68),
(Warnock 69), (Watkins 70) and (Archuleta 72).
Inspite of all the activity and surveying of the literature,
no quantitative commensurate study of the different methods has been
attempted. In particular, the performance tables at the end of
(Sutherland et al 1973) are subjective evaluations rather than
experimental results of benchmark problems, as the authors clearly
state. Continuing in the same subjective fashion, OCCULT is fast in
that it can generate simple scenes (200 edges) of blocks in
less than a second; the arm animation (524 edges) requires four to
six seconds; the starship Enterprise (1230 edges) requires ten to
twelve seconds; and the largest scenes that fit in core (4000 edges)
take from thirty to sixty seconds.{I∂200,630;H2;X0.6;*STRSHP.PLT;